package com.sheng.leetcode.year2023.month12.day01;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author by ls
 * @date 2023/12/1
 * <p>
 * 2661. 找出叠涂元素<p>
 * <p>
 * 给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵 mat 。arr 和 mat 都包含范围 [1，m * n] 内的 所有 整数。<p>
 * 从下标 0 开始遍历 arr 中的每个下标 i ，并将包含整数 arr[i] 的 mat 单元格涂色。<p>
 * 请你找出 arr 中在 mat 的某一行或某一列上都被涂色且下标最小的元素，并返回其下标 i 。<p>
 * <p>
 * 示例 1：<p>
 * image explanation for example 1<p>
 * 输入：arr = [1,3,4,2], mat = [[1,4],[2,3]]<p>
 * 输出：2<p>
 * 解释：遍历如上图所示，arr[2] 在矩阵中的第一行或第二列上都被涂色。<p>
 * <p>
 * 示例 2：<p>
 * image explanation for example 2<p>
 * 输入：arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]<p>
 * 输出：3<p>
 * 解释：遍历如上图所示，arr[3] 在矩阵中的第二列上都被涂色。<p>
 * <p>
 * 提示：<p>
 * m == mat.length<p>
 * n = mat[i].length<p>
 * arr.length == m * n<p>
 * 1 <= m, n <= 10^5<p>
 * 1 <= m * n <= 10^5<p>
 * 1 <= arr[i], mat[r][c] <= m * n<p>
 * arr 中的所有整数 互不相同<p>
 * mat 中的所有整数 互不相同<p>
 */
public class LeetCode2661 {

    @Test
    public void test01() {
//        int[] arr = {1, 3, 4, 2};
//        int[][] mat = {{1, 4}, {2, 3}};
        int[] arr = {2, 8, 7, 4, 1, 3, 5, 6, 9};
        int[][] mat = {{3, 2, 5}, {1, 4, 6}, {8, 7, 9}};
        System.out.println(new Solution().firstCompleteIndex(arr, mat));
    }
}

class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        // 将包含整数 arr[i] 的 mat 单元格涂色
        // 每次对 mat 染色时，都判断一下当前行/列，是否已经全部被染色，如果全部被染色，则返回
        Map<Integer, int[]> map = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 集合的 key 为数组 mat 中的元素，value 为索引
                map.put(mat[i][j], new int[]{i, j});
            }
        }
        int[] nums1 = new int[m], nums2 = new int[n];
        for (int i = 0; i < n * m; i++) {
            int[] ints = map.get(arr[i]);
            int x = ints[0], y = ints[1];
            // 判断是否存在行/列已经染色完毕
            if (++nums1[x] == n || ++nums2[y] == m) {
                return i;
            }
        }
        return -1;
    }
}
